#include <iostream>
#include <BinaryTree.hpp>

using namespace std;

// inorder [left,root,right]
// postorder[left,right,root]

class Solution
{
public:
    TreeNode *Helper(int startIn, int endIn, int startPost, int endPost, vector<int> &inorder, vector<int> &postorder)
    {
        if (endIn < startIn)
        {
            return nullptr;
        }
        TreeNode *root = new TreeNode(postorder[endPost]);
        auto rootIt = find(inorder.begin() + startIn, inorder.begin() + endIn, root->val);
        int index = rootIt - inorder.begin();
        int leftSize = index - startIn;
        root->right = Helper(index + 1, endIn, startPost + leftSize, endPost - 1, inorder, postorder);
        root->left = Helper(startIn, index - 1, startPost, startPost + leftSize - 1, inorder, postorder);
        return root;
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
    {
        return Helper(0, inorder.size() - 1, 0, postorder.size() - 1, inorder, postorder);
    }
};

int main()
{
    cout << "Code106" << endl;
    Solution s;
    vector<int> in{9, 3, 15, 20, 7};
    vector<int> post{9, 15, 7, 20, 3};
    TreeNode *root = s.buildTree(in, post);
    PrintTreeByWide(root, "null", 3);
    return 0;
}